#include<stdio.h>
#define _CRT_SECURE_NO_WARNINGS
#define V 6

int min_key(int key[], bool visited[]) {
	int min = 2147483647, min_index;  //遍历 key 数组使用，min 记录最小的权值，min_index 记录最小权值关联的顶点
	for (int i = 0; i < V; i++) {
		if (visited[i] == false && key[i] < min) {
			min = key[i];
			min_index = i;
		}
	}
	return min_index;
}
//输出
void print_prim(int parent[], int cost[V][V]) {
	int minCost = 0;
	printf("最小生成树为：\n");
	for (int i = 1; i < V; i++) {
		//parent 数组下标值表示各个顶点，各个下标对应的值为该顶点的父节点
		printf("%d - %d wight:%d\n", parent[i] + 1, i + 1, cost[i][parent[i]]);//由于数组下标从 0 开始，因此输出时各自 +1
		minCost += cost[i][parent[i]];
	}
	printf("总权值为：%d", minCost);
}

void find_prim(int cost[V][V]) {
	int parent[V], key[V];
	bool visited[V];
	// 初始化 3 个数组
	for (int i = 0; i < V; i++) {
		key[i] = 2147483647;    // 将 key 数组各个位置设置为无限大的数
		visited[i] = false;     // 所有的顶点全部属于 B 类
		parent[i] = -1;         // 所有顶点都没有父节点
	}

	key[0] = 0;
	parent[0] = -1;//表名该节点没有父节点


	//对于n个结点的图，最多需要n-1条路径就可以形成最小生成树
	for (int  i =0 ; i < V-1; i++)
	{
		int u = min_key(key, visited);
		visited[u] = true;//该结点标识到A类

		//因为A类中的数据有变化，所以将A类中的数据进行更新
		for (int v = 0; v < V; v++) {
			// 如果类 B 中存在到下标为 u 的顶点的权值比 key 数组中记录的权值还小，表明新顶点的加入，使得类 B 到类 A 顶点的权值有了更好的选择
				if (cost[u][v] != 0 && visited[v] == false && cost[u][v] < key[v])
				{
					// 更新 parent 数组记录的各个顶点父节点的信息
					parent[v] = u;
					// 更新 key 数组
					key[v] = cost[u][v];
				}
		}
	}
	print_prim(parent, cost);
}

int main() {
	int p1, p2;
	int weight;
	int cost[V][V] = { 0 };
	printf("输入图（顶点到顶点的路径和权值)：\n");
	while (1) {
		printf("如果输入（-1，-1）退出：");
		scanf("%d,%d", &p1, &p2);
		if (p1 == -1 && p2 == -1) {
			break;
		}
		scanf("%d", &weight);
		cost[p1 - 1][p2 - 1] = weight;
		cost[p2 - 1][p1 - 1] = weight;
	}
	find_prim(cost);
	return 0;
}